package com.LeetCode.why57;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Created by Aqc on 2017/6/18.
 */

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

public class InsertInterval {
    public static List<Interval> mergeEnd(List<Interval> intervals, int nEnd, Interval temp, int i) {
        for (int j = i; j < intervals.size(); j++) {
            if (j == intervals.size() - 1 || nEnd < intervals.get(j + 1).start) {
                temp.end = nEnd;
                return intervals;
            } else if (nEnd >= intervals.get(j + 1).start && nEnd <= intervals.get(j + 1).end) {
                temp.end = intervals.get(j + 1).end;
                intervals.remove(j + 1);
                return intervals;

            } else if (nEnd > intervals.get(j + 1).end) {
                intervals.remove(j + 1);
                j--;
            }
        }
        return null;
    }

    public static List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (intervals.size() == 0) {
            List<Interval> res = new ArrayList<>();
            res.add(newInterval);
            return res;
        }

        int nStart = newInterval.start;
        int nEnd = newInterval.end;
        for (int i = 0; i < intervals.size(); i++) {
            Interval temp = intervals.get(i);
            if (temp.start > nStart && temp.start > nEnd) {
                //列表首插入,并return
                intervals.add(intervals.get(intervals.size() - 1));
                for (int j = intervals.size() - 1; j > i; j--) {
                    intervals.set(j, intervals.get(j - 1));
                }
                intervals.set(i, newInterval);
                return intervals;

            }
            if (nStart <= temp.start && nEnd >= temp.end) {
                //start和end都并
                temp.start = nStart;

                return mergeEnd(intervals, nEnd, temp, i);
            }
            if (temp.start > nStart &&
                    temp.start <= nEnd && temp.end >= nEnd) {
                //start并
                temp.start = nStart;
                return intervals;
            }
            if (nStart > temp.start && nEnd < temp.end) {
                //新区间夹在中间
                return intervals;
            }
            if (nStart > temp.start && nStart <= temp.end &&
                    nEnd > temp.end) {
                //end并
                return mergeEnd(intervals, nEnd, temp, i);


            }

        }
        //列表末尾添加
        intervals.add(newInterval);
        return intervals;

    }

    public static void main(String[] args) {
        List<Interval> test = new ArrayList<>();
        test.add(new Interval(3, 5));
        test.add(new Interval(12, 15));
        //test.add(new Interval(15, 18));
        List<Interval> result = InsertInterval.insert(test, new Interval(6, 7));
        Iterator<Interval> it = result.listIterator();
        while (it.hasNext()) {
            Interval temp = it.next();
            System.out.println("[" + temp.start + "," + temp.end + "]");
        }

    }

}
